package com.haidechizi.sort;


import java.util.Arrays;

/**
 * 快速排序
 * <p>
 * 1.选择数组的第一个数为基数
 * <p>
 * 2.将大于基数的数移到数组右边
 * <p>
 * 3.将小于基数的数移到数组左边
 * <p>
 * 4.将基数放置到中间位置（高位和地位到达的位置）
 * <p>
 * 5.对数组左右两个进行递归排序
 * <p>
 * 时间复杂度：O(nlogn)
 * <p>
 * 空间复杂度：O(nlogn)
 */
public class QuickSort {

    public void quickSort(int[] arr, int start, int end) {
        // 当左右重合时，递归结束
        if (start >= end) {
            return;
        }

        int position = arr[start];
        int low = start;
        int high = end;

        // 当
        while (low < high) {
            // 先比较高位的值
            while (low < high && arr[high] >= position) {
                high--;
            }
            arr[low] = arr[high];
            while (low < high && arr[low] < position) {
                low++;
            }
            arr[high] = arr[low];
        }

        arr[low] = position;

        // 递归数组左侧的数据
        quickSort(arr, start, low);

        // 递归数组右侧的数据
        quickSort(arr, low + 1, end);
    }

    public static void main(String[] args) {
        int[] arr = new int[]{2, 7, 4, 6, 5, 0, 7, 9, 4, 8, 5, 7, 5};
        new QuickSort().quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}
